//
// Created by win10 on 24-11-13.
//

//链式结构的  栈
//头节点 =》》 an==》an-1==》。。。==》a1
//           栈顶
//所有的操作（插入，删除），都会在栈顶进行 换句话来说
//所有的节点的插入或者删除 都在 头节点之后进行

#include <stdio.h>
#include <malloc.h>
#include <math.h>
//定义节点结构
typedef struct{
    //数据域
    int data;
    //指针域
    struct Node * next;//指针变量的类型是什么？ 指针指向谁==》下一个节点 Node 类型保持一致

}Node;

//2.定义头节点的结构
typedef struct{
  //栈的相关信息
  int size;//栈的长度
  //栈的容量==》空间容量
//  int capacity;
  //头指针 指向节点 和节点的数据类型保持一致
  struct Node * top;
}Stack;

//3.创建/初始化 栈
//返回一个栈的地址
Stack * createStack(){
  //为栈 开辟一个动态的空间 ==》malloc
  Stack * s = (Stack *)malloc(sizeof(Stack));
  //判断 栈的空间是否创建完毕
  if(s == NULL){//==>内存空间已满 创建失败
    printf("space is full\n");
    return NULL;
    }
    //定义头指针和size，此时头指针没有指向的节点 为空
    s->top = NULL;
    s->size = 0;
    return s;//栈的地址
}

//4.判断是否为空
int isEmpty(Stack * s) {
  //根据size来判断 栈 是否为空
  return s->size == 0;
}

//5.入栈操作
void push(Stack * s, int value) {
  //为新节点 分配空间
  Node * newNode = (Node *)malloc(sizeof(Node));

  //判断空间是否分配成功
  if(newNode == NULL) {
    printf("space is full\n");
    return;
  }
  //为新节点的数据放入元素
  newNode->data = value;
  //更新新节点的指针域
  newNode->next = s->top;
  //更新头节点的指针域
  s->top = newNode;
  s->size++;
}

//删除操作
int pop(Stack * s) {
  //判断栈是否为空
  if(isEmpty(s)) {
    printf("stack is empty\n");
    return -1;//表示程序出错
  }
  //定位到要被出栈的节点
  //仅会出栈头节点之后的节点
  Node * temp = s->top;//用临时指针存储要出栈的节点
  int value= temp->data;
  //头节点的指针域 更新
  s->top = temp->next;//s.top=s.top.next
  free(temp);//释放节点
  s->size--;
  return value;
}

//7.销毁栈
//释放所有空间
void display(Stack * s) {
  //栈不为空 一直出栈
  while(!isEmpty(s)) {
  pop(s);
  }
  free(s);
  printf("stack has been destroyed");
}

void decimaltoOctal(int n) {
  //创建一个栈
  Stack * s = createStack();
  //做一个循环 十进制转换成八进制
  while (n>0) {
    int remainder=n%8;
    push(s, remainder);
    n/=8;
  }
  //八进制的值输出出来
  while(!isEmpty(s)) {
    printf("%d",pop(s));
  }
  printf("\n");
  display(s);
}

//二进制转十进制
int ten(const char * n) {
  //创建一个栈
  Stack * s = createStack();
  for(int i=0;n[i]!='\0';i++) {
    push(s, n[i]-'0');
  }
  int decimal=0;
  int position=0;
  while(!isEmpty(s)) {
    int bit=pop(s);
    decimal=decimal+bit*pow(2,position);
    position++;
  }
  printf("%d\n",decimal);
  return decimal;

}


int factorial(int n) {
  Stack * s = createStack();

  int result = 1;//出口
   //递归
  for(int i=n;i>=1;i--) {
    push(s, i);
  }

  //出栈
  while(!isEmpty(s)) {
    result*=pop(s);
  }

  display(s);
  return result;
}


int main(void){
  // Stack * s = createStack();
  // //入栈
  // push(s,1);
  // push(s,2);
  // push(s,3);
  // //出栈
  // printf("%d\n",pop(s));
  // printf("%d\n",pop(s));
  // printf("%d\n",pop(s));

  // decimaltoOctal(159);

  // ten('0011');
  const char * n="1010";
  ten(n);
  printf("%d\n",factorial(4));
}
